1. Field of the Invention
The invention disclosed and claimed herein generally pertains to a method for partitioning the simulation processes of a null message-based parallel and distributed discrete event simulation (PDES). More particularly, the invention pertains to a method of the above type wherein the workload comprises a number of logical processes (LPs), and a metric related to progression rate or simulation speed is used to select a particular partitioning, which is applied to the LPs to enhance overall simulation performance.
2. Description of the Related Art
As is known by those of skill in the art, discrete event simulation is used to represent the operation of a physical system as a chronological sequence of events. Physical processes of the system are simulated by one or more logical processes (LPs), which may each comprise a sequential discrete event simulation program. A discrete event simulation can be viewed as a sequence of event computations, wherein each computed event has a time stamp indicating when that event occurs in the physical system. The collective simulations of one or more LPs comprise a simulation workload. As used herein, “virtual time” is the time of an event or physical process in the physical system. “Run time” is the amount of time an LP uses to simulate a physical process.
In parallel and distributed discrete event simulation (PDES), multiple LPs of the above type are provided, and different LPs are respectively executed on two or more data processors or computing devices. PDES is used to model the behavior of physical systems in application fields such as telecommunication networks, digital logic circuits and transportation, by way of example. In PDES, each LP in a group of LPs may be connected over links or channels to each of the other LPs. The LPs communicate with each other by sending time-stamped events to one another over the links or channels. An LP may thus receive time-stamped events from two or more of such LPs. However, it is very important for each LP to always process events in time-stamp order. Because of this requirement, a condition known as deadlock can occur, which is discussed hereinafter in further detail. To avoid deadlock in PDES, a procedure for transmitting null messages may be used, as likewise discussed hereinafter.
As is further well known by those of skill in the art, a simulation workload in PDES can be partitioned, in an effort to maximize simulation performance. In PDES, partitioning is carried out by assigning each LP in a plurality of LPs, which collectively perform the simulation, to one of a plurality of sets or groups. Each set corresponds to a different one of a plurality of computing devices, and each LP of a set is intended for execution by the computing device corresponding to that set. The LPs of different sets can thus be executed simultaneously, or in parallel.
In order to maximize simulation performance gain, the partitioning effort should minimize the impact of inter-LP communication delays and balance the computing resource requirement in each set of LPs. Yet these two goals are sometimes conflicting. Further, it is often the case that not all of the inter-LP communication delays can be minimized. Therefore the partitioning effort should identify and prioritize the most critical LPs in terms of simulation performance. However, due to the lack of an accurate and quantitative performance model, currently available solutions to simulation workload partitioning suffer certain drawbacks, when they are applied to null-message based PDES. For example, existing partitioning approaches typically cannot identify the most critical task LPs, and are not able to quantitatively evaluate their impact on the simulation performance. In addition, existing partitioners used by these simulation partitioning approaches only measure the impact of the communication traffic, but not the overall simulation performance. For example, one solution uses rule of thumb to identify LPs which might be the critical task LPs, and then uses a pre-processing step to force the partitioner to assign all of these critical task LPs to the same computing device. However, the partitioning goals of balancing computation and prioritizing critical LPs may conflict with each other. Without a quantitative measure, it can be very difficult to achieve an optimal partitioning result.